//1.最原始无优化版本
class Solution {
public:
    vector<vector<bool>> visited;
    int target_size;
    int m,n;

bool act(int i, int j, int k, vector<vector<char>>& board, string& word) {
    if (i < 0 || i >= m || j < 0 || j >= n) return false;
    if (visited[i][j] || board[i][j] != word[k]) return false;
    if (k == target_size - 1) return true;  // 最后一个字符匹配成功

    visited[i][j] = true;
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    for (int dir = 0; dir < 4; ++dir) {
        int new_r = i + dr[dir];
        int new_c = j + dc[dir];
        if (act(new_r, new_c, k + 1, board, word)) {
            //visited[i][j] = false; // 可以不用
            return true;
        }
    }

    visited[i][j] = false;
    return false;
}

    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();
        n = board[0].size();
        visited.assign(m, vector<bool>(n, false));
        target_size = word.size();

        bool result = false;   

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == word[0]) {
                    result = act(i, j, 0, board, word);
                    if (result == true) return true;
                }
            }
        }
        return false;
    }
};
//2.频次优化+翻转字母
class Solution {
public:
    vector<vector<bool>> visited;
    int target_size;
    int m,n;

    bool act(int i, int j, int k, vector<vector<char>>& board, string& word) {
        if (i < 0 || i >= m || j < 0 || j >= n) return false;
        if (visited[i][j] || board[i][j] != word[k]) return false;
        if (k == target_size - 1) return true;  // 最后一个字符匹配成功

        visited[i][j] = true;
        int dr[] = {-1, 1, 0, 0};
        int dc[] = {0, 0, -1, 1};

        for (int dir = 0; dir < 4; ++dir) {
            int new_r = i + dr[dir];
            int new_c = j + dc[dir];
            if (act(new_r, new_c, k + 1, board, word)) 
                return true;
        }
        visited[i][j] = false;
        return false;
    }

    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();
        n = board[0].size();
        visited.assign(m, vector<bool>(n, false));
        target_size = word.size();

        // ✅ 优化1：频次剪枝
        unordered_map<char,int> freq_board, freq_word;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                freq_board[board[i][j]]++;
            }
        }
        for (char c : word) {
            freq_word[c]++;
        }
        for (auto &[L, R] : freq_word) {
            if (freq_board[L] < R) {
                return false; // board中字母数量不足，直接剪枝
            }
        }

        // ✅ 优化2：从稀有字母开始
        // 如果 word[0] 在 board 中出现次数 > word.back() 的次数，
        // 可以考虑反转 word，从稀有字母开始搜索，减少分支。
        if (freq_board[word[0]] > freq_board[word.back()]) {
            reverse(word.begin(), word.end());
        }

        // 正常 DFS 搜索
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == word[0]) {
                    if (act(i, j, 0, board, word)) return true;
                }
            }
        }
        return false;
    }

};



